package _binary_search;

/**
 * 528. 按权重随机选择
 */
public class No528 {
    private final int[] preSum;
    private final int sum;

    public No528(int[] w) {
        int n = w.length;
        preSum = new int[n];
        preSum[0] = w[0];
        for (int i = 1; i < n; i++) {
            preSum[i] = preSum[i - 1] + w[i];
        }
        sum = preSum[n - 1];
    }

    public int pickIndex() {
        int target = (int) (Math.random() * sum) + 1;
        return lowerBound(target);
    }

    private int lowerBound(int target) {
        int left = 0, right = preSum.length - 1;
        while (left <= right) {
            int mid = left + (right - left >> 1);
            if (preSum[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}
